def mod_exp(x,y,mod):
res = 1
while (y):
if (y % 2 == 0):
x = (x * x) % mod
y = y // 2
else:
y -= 1
res = (res * x) % mod
return res % mod
t = int(input())
for _ in range(t):
n = int(input())
s = input()
count = 1
last_element = s[0]
last_element_contig_len = 1
for i in range(1,n):
if (s[i]==last_element):
last_element_contig_len +=1
else:
last_element = s[i]
last_element_contig_len = 1
count += mod_exp(2, (last_element_contig_len - 1), 998244353)
print (count % 998244353)
#include <iostream>
#include <string>
#include <algorithm>
#include <climits>
#include <cmath>
#include <stdlib.h>
#include <vector>
#include <utility>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <iomanip>
using namespace std;
#define int unsigned long long int
#define f(i,a,n) for(int i = a; i < n; i++)
#define pii pair<int, int>
#define ff first
#define ss second
#define len(vec) (vec).size()
#define vi vector<int>
#define pb push_back
#define mp make_pair
int inf = LONG_LONG_MAX;
int mod = 998244353;
vi dp;
void tathastu()
{
int n;
cin>>n;
string s;
cin>>s;
int one=0,zero=0, ans=0,used=0;
string a;
f(i,0,n)
{
one+=s[i]=='1';
zero+=s[i]=='0';
int l=i+1;
if(s[i]=='1')
{
int req=(l-one);
used+=req;
int rem=(l-1)-used;
int val=(dp[rem])%mod;
ans=(ans+val)%mod;
one+=req;
}
else
{
int req=(l-zero);
used+=req;
int rem=(l-1)-used;
int val=(dp[rem])%mod;
ans=(ans+val)%mod;
zero+=req;
}
}
cout<<(ans%mod)<<"\n";
}
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int testcases;
cin>>testcases;
dp.resize(2*1e5+1);
dp[0]=1;
f(i,1,2*1e5+1)
dp[i]=(dp[i-1]*2)%mod;
while(testcases--)
tathastu();
return 0;
}274. H-Index | 260. Single Number III |
240. Search a 2D Matrix II | 238. Product of Array Except Self |
229. Majority Element II | 222. Count Complete Tree Nodes |
215. Kth Largest Element in an Array | 198. House Robber |
153. Find Minimum in Rotated Sorted Array | 150. Evaluate Reverse Polish Notation |
144. Binary Tree Preorder Traversal | 137. Single Number II |
130. Surrounded Regions | 129. Sum Root to Leaf Numbers |
120. Triangle | 102. Binary Tree Level Order Traversal |
96. Unique Binary Search Trees | 75. Sort Colors |
74. Search a 2D Matrix | 71. Simplify Path |
62. Unique Paths | 50. Pow(x, n) |
43. Multiply Strings | 34. Find First and Last Position of Element in Sorted Array |
33. Search in Rotated Sorted Array | 17. Letter Combinations of a Phone Number |
5. Longest Palindromic Substring | 3. Longest Substring Without Repeating Characters |
1312. Minimum Insertion Steps to Make a String Palindrome | 1092. Shortest Common Supersequence |